package com.gitee.wsl.struct.graph

 interface MapGraph<T> : Map<MapGraph.Vertex<T>, List<MapGraph.Edge<T>>> {

     var renderer: (Any?.() -> String)

     val circularVertexes: Map<T, List<Edge<T>>>
        get() {
            val circularDependencies: MutableMap<T, MutableList<Edge<T>>> = mutableMapOf()
            val visited: MutableSet<Vertex<T>> = mutableSetOf()

            for (vertex: Vertex<T> in keys) {
                if (vertex !in visited) {
                    val path: MutableList<Vertex<T>> = mutableListOf()
                    vertex.deepFirstSearchCircularDependencies(visited, path, circularDependencies)
                }
            }

            return circularDependencies.mapValues { it.value.toList() }
        }

     val hasCircularVertexes: Boolean
        get() = circularVertexes.isNotEmpty()

     val duplicatedVertexes: Map<T, Int>
        get() = keys.groupingBy(Vertex<T>::value).eachCount().filterValues { it > 1 }

     val hasDuplicatedVertexes: Boolean
        get() = duplicatedVertexes.isNotEmpty()

     val missingVertexes: Set<T>

     val hasMissingVertexes: Boolean
        get() = missingVertexes.isNotEmpty()

     fun asString(): String = buildString {
        this@MapGraph.forEach { (vertex: Vertex<T>, edges: List<Edge<T>>) ->
            val value: String = renderer(vertex.value)
            val edgeString: String = edges.joinToString { renderer(it.destination.value) }
            appendLine("$value -> [$edgeString]")
        }
    }

     operator fun contains(value: T): Boolean = keys.any { it.value == value }

     fun contains(value: T, predicate: (T) -> Boolean): Boolean =
        keys.any { predicate(it.value) }

     fun containsCircularVertexes(value: T): Boolean =
        circularVertexes[value]?.isNotEmpty() == true

     fun doesNotContainsCircularVertexes(value: T): Boolean = !containsCircularVertexes(value)

     fun vertexesFor(value: T, predicate: (T) -> Boolean = { it == value }): List<T> {
        if (containsCircularVertexes(value)) return emptyList()
        val vertex: Vertex<T> = keys.find { predicate(it.value) } ?: return emptyList()
        val edges: List<Edge<T>> = this[vertex] ?: return emptyList()
        val destinationVertexes: Sequence<Vertex<T>> = edges.asSequence().map(Edge<T>::destination)
        val destinations: Sequence<T> = destinationVertexes.map(Vertex<T>::value)
        return (destinations + destinationVertexes.flatMap { vertexesFor(it.value) }).toList()
    }

     fun vertexesFor(vararg values: T): List<T> = values.flatMap(::vertexesFor)

     fun toGraphSortedByEdges(): MapGraph<T> = buildGraph {
        val sortedGraph: MutableMapGraph<T> = this
        val graph: MapGraph<T> = this@MapGraph
        val remainingMap: MutableMap<Vertex<T>, List<Edge<T>>> = graph.toMutableMap()
        while (remainingMap.isNotEmpty()) {
            val vertexesToBeRemoved: MutableList<Vertex<T>> = mutableListOf()
            for ((vertex: Vertex<T>, edges: List<Edge<T>>) in remainingMap) {
                if (edges.isEmpty()) {
                    sortedGraph.addVertex(vertex.value)
                    vertexesToBeRemoved.add(vertex)
                }
                for (edge: Edge<T> in edges) {
                    if (edge.destination.value in sortedGraph.keys.map(Vertex<T>::value)) {
                        sortedGraph.addVertex(edge.source.value)
                        sortedGraph.addEdge(edge.source.value, edge.destination.value)
                        vertexesToBeRemoved.add(edge.source)
                    }
                }
            }
            for (vertexToBeRemoved: Vertex<T> in vertexesToBeRemoved) {
                remainingMap.remove(vertexToBeRemoved)
            }
            vertexesToBeRemoved.clear()
        }
    }

     fun renderer(block: Any?.() -> String) {
        this.renderer = block
    }

     data class Vertex<T>(val index: Int, val value: T) {
        override fun toString(): String = "$value"
    }

     data class Edge<T>(val source: Vertex<T>, val destination: Vertex<T>) {

         constructor(
            source: Pair<Int, T>,
            destination: Pair<Int, T>,
        ) : this(Vertex(source.first, source.second), Vertex(destination.first, destination.second))

        override fun toString(): String = "[$source -> $destination]"
    }

    private fun Vertex<T>.deepFirstSearchCircularDependencies(
        visited: MutableSet<Vertex<T>>,
        path: MutableList<Vertex<T>>,
        circularDependencies: MutableMap<T, MutableList<Edge<T>>>,
    ) {
        val map: MapGraph<T> = this@MapGraph
        val vertex: Vertex<T> = this
        visited.add(vertex)
        path.add(vertex)

        val edges: List<Edge<T>> = map[vertex] ?: return

        for (edge: Edge<T> in edges) {
            val destination: Vertex<T> = edge.destination

            if (destination in path) {
                val circularPath: MutableList<Vertex<T>> =
                    path.subList(path.indexOf(destination), path.size)
                val circularEdges: List<Edge<T>> =
                    circularPath.zipWithNext { from: Vertex<T>, to: Vertex<T> -> Edge(from, to) } +
                        Edge(circularPath.last(), circularPath.first())
                circularDependencies
                    .getOrPut(circularPath.first().value) { mutableListOf() }
                    .addAll(circularEdges)
            } else if (destination !in visited) {
                destination.deepFirstSearchCircularDependencies(visited, path, circularDependencies)
            }
        }

        if (path.last() == vertex) {
            path.remove(vertex)
        }
    }
}

 fun <T> buildGraph(builderAction: MutableMapGraph<T>.() -> Unit = {}): MapGraph<T> =
    MutableMapGraph<T>().apply(builderAction)

